import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Set;

/**
 * 操作系统页面置换算法
 * LRU 最近最久未使用置换算法，通过 LinkedHashMap 实现
 */
public class LRUCache {

    private LinkedHashMap<Integer, Integer> cache;
    private int capacity;

    /**
     * 初始化构造函数
     * @param capacity 容量
     */
    public LRUCache(int capacity) {
        cache = new LinkedHashMap<>(capacity);
        this.cache = cache;
    }

    /**
     * 拿出数据
     * @param key key 键
     * @return value 键
     */
    public int get(int key) {
        // 缓存中不存在此 key，直接返回
        if (!cache.containsKey(key)) {
            return -1;
        }

        int res = cache.get(key);
        cache.remove(key);      // 先从链表中删除
        cache.put(key, res);    // 再把该节点放到链表末尾处
        return res;
    }

    /**
     * 插入键值对
     * @param key key 键
     * @param value value 键
     */
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            cache.remove(key); // 已经存在，在当前链表移除
        }
        if (capacity == cache.size()) {
            // cache 已满，删除链表头位置
            Set<Integer> keySet = cache.keySet();
            Iterator<Integer> iterator = keySet.iterator();
            cache.remove(iterator.next());
        }
        cache.put(key, value); // 插入到链表末尾
    }

}
